Search for: All records

We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of (Buchbinder, Feldman, Seffi, and Schwartz [14] and Censor-Hillel, Levy, and Shachnai [16]), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O (n1-Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 1/2. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 1/2 is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun [37]) and space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan [35]). In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. 

We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of (Buchbinder, Feldman, Seffi, and Schwartz [14] and Censor-Hillel, Levy, and Shachnai [16]), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O (n1-Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 1/2. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 1/2 is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun [37]) and space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan [35]). In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. 

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where n parties, each holding an input bit, wish to know each other’s input. For this, they communicate in rounds, where, in each round, one designated party sends a bit to all other parties over a channel governed by an adversary that may corrupt a constant fraction of the received communication. We mention that the dissemination problem was studied in the stochastic noise model since the 80’s. While stochastic noise in multi-party channels has received quite a bit of attention, the case of adversarial noise has largely been avoided, as such channels cannot handle more than a 1/n-fraction of errors. Indeed, this many errors allow an adversary to completely corrupt the incoming or outgoing communication for one of the parties and fail the protocol. Curiously, we show that by eliminating these "trivial" attacks, one can get a simple protocol resilient to a constant fraction of errors. Thus, a model that rules out such attacks is both necessary and sufficient to get a resilient protocol. The main shortcoming of our dissemination protocol is its length: it requires Θ(n²) communication rounds whereas n rounds suffice in the absence of noise. Our main result is a matching lower bound of Ω(n²) on the length of any dissemination protocol in our model. Our proof first "gets rid" of the channel noise by converting it to a form of "input noise", showing that a noisy dissemination protocol implies a (noiseless) protocol for a version of the direct sum gap-majority problem. We conclude the proof with a tight lower bound for the latter problem, which may be of independent interest. 

We give an $$\widetilde{O}(\sqrt{n})$$-space single-pass 0.483-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on n vertices. This improves over an $$O(\log n)$$-space $4 / 9 < 0.45$ approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for $$o(\sqrt{n})$$-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with $$\widetilde{O}(\sqrt{n})$$- space can provably outperform $$o(\sqrt{n})$$- space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max-DICUT algorithms, including the “oblivious” algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with $$\ell_{1}$$ errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the $$O(\log n)$$-space algorithm for Max-DICUT, and can roughly be characterized as based on “zeroth” order snapshots. Our work thus opens the possibility of a new class of algorithms for approximating CSPs by demonstrating that more sophisticated snapshots can outperform cruder ones in the case of Max-DICUT. 

We consider prophet inequalities subject to feasibility constraints that are the intersection of q matroids. The best-known algorithms achieve a Θ(q)-approximation, even when restricted to instances that are the intersection of q partition matroids, and with i.i.d. Bernoulli random variables [José R. Correa et al., 2022; Moran Feldman et al., 2016; Marek Adamczyk and Michal Wlodarczyk, 2018]. The previous best-known lower bound is Θ(√q) due to a simple construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] (which uses i.i.d. Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of q^{1/2+Ω(1/log log q)} by writing the construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with p^p disjoint cliques of size p, using recent techniques developed in [Noga Alon and Ryan Alweiss, 2020].